//Given an array nums of size n, return the majority element. 
//
// The majority element is the element that appears more than ⌊n / 2⌋ times. You
// may assume that the majority element always exists in the array. 
//
// 
// Example 1: 
// Input: nums = [3,2,3]
//Output: 3
// Example 2: 
// Input: nums = [2,2,1,1,1,2,2]
//Output: 2
// 
// 
// Constraints: 
//
// 
// n == nums.length 
// 1 <= n <= 5 * 104 
// -231 <= nums[i] <= 231 - 1 
// 
//
// 
//Follow-up: Could you solve the problem in linear time and in O(1) space? Relat
//ed Topics Array Hash Table Divide and Conquer Sorting Counting 
// 👍 6268 👎 280


package leetcode.editor.en;

public class _169_MajorityElement {
    public static void main(String[] args) {
        Solution solution = new _169_MajorityElement().new Solution();
        int i = solution.majorityElement(new int[]{0, 1, 2, 3, 3, 3, 3});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int majorityElement(int[] nums) {
            int result = nums[0], count = 1;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] == result){
                    count++;
                }else {
                    if (--count==0){
                        count = 1;
                        result = nums[i];
                    }
                }
            }
            return result;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}